package JZOffer;

import java.util.ArrayList;

public class _23_ {
    class Solution {
        private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
        private ArrayList<Integer> list = new ArrayList<Integer>();
        public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
            if (root == null) return listAll;
            list.add(root.val);
            target -= root.val;
            if (target == 0 && root.left == null && root.right == null)
                listAll.add(new ArrayList<Integer>(list));
            FindPath(root.left, target);
            FindPath(root.right,target);
            list.remove(list.size()-1);
            return listAll;
        }
    }

    Solution getSolution() {
        return new Solution();
    }

    public static void main(String args[]) {
        _23_ c = new _23_();
        _23_.Solution s = c.getSolution();
        TreeNode L1 = new TreeNode(3);
        TreeNode L2 = new TreeNode(4);
        TreeNode L3 = new TreeNode(10);
        TreeNode L4 = new TreeNode(6);
        TreeNode L5 = new TreeNode(7);
        L1.left = L2;
        L1.right = L3;
        L2.left = L4;
        L2.right = L5;
//        System.out.println(L1,7);
        ArrayList<ArrayList<Integer>> res = s.FindPath(L1,13);
        for (ArrayList<Integer> arrlist:
        res){
            System.out.println("----------------------");
            for (Integer item :
                    arrlist) {
                System.out.println(item);
            }
        }
    }
}
